package words.libsvm;
import java.util.*;

public class RelationKernel
{
  static final int DEFAULT_FORE = 4;
  static final int DEFAULT_INTRA = 4;
  static final int DEFAULT_AFTER = 4;
  static final double DEFAULT_LAMBDA = 0.75;
  static final boolean DEFAULT_CACHE = true; 
  static final boolean DEFAULT_NORM = true; 

  // max length of fore subseq
  int m_nFore;
  // max length of intra subseq
  int m_nIntra;
  // max length of after subseq
  int m_nAfter;
  // gap penalty
  double m_lambda;
  // true if cached self kernels
  boolean m_bCache;
  // true if normalized kernels
  boolean m_bNorm;
	
  protected HashMap m_mapStoK;

  public RelationKernel(int nFore, int nIntra, int nAfter,
			double lambda, boolean bCache, boolean bNorm)
  {
    m_nFore = nFore;
    m_nIntra = nIntra;
    m_nAfter = nAfter;
    m_lambda = lambda;
    m_bCache = bCache;
    m_bNorm = bNorm;

    m_mapStoK = new HashMap();
  }

  public RelationKernel() 
  {
    m_nFore = DEFAULT_FORE;
    m_nIntra = DEFAULT_INTRA;
    m_nAfter = DEFAULT_AFTER;
    m_lambda = DEFAULT_LAMBDA;
    m_bCache = DEFAULT_CACHE;
    m_bNorm = DEFAULT_NORM;

    m_mapStoK = new HashMap();
  }


  /**
     Computes the normalized string kernel between two strings.
     @param s1 string 1
     @param s2 string 2
     @return normalized value, with 1 for exact match.
  */
  public double kernel(String[] s1, String[] s2)
  {
    double k1 = selfKernel(s1);
    double k2 = selfKernel(s2);
    
    double k = singleKernel(s1, s2);
    if (k == 0)
      return 0;

    assert k1 != 0;
    assert k2 != 0;

    // normalize
    return k / Math.sqrt(k1 * k2);
  }
  
  
  public double selfKernel(String[] s)
  {
    if (m_bCache) {
      // get string representation of relation instance
      String strText = "";
      for (int i = 0; i < s.length; i++)
	strText += s[i] + " ";
      // get cached value
      Double dblk = (Double) m_mapStoK.get(strText);
      if (dblk == null) {
	double k = singleKernel(s, s);
	m_mapStoK.put(strText, new Double(k));
	return k;
      }
      return dblk.doubleValue();
    }

    return singleKernel(s, s);
  }
  

  public double singleKernel(String[] s1, String[] s2)
  {
    int e1 = getLeftEntity(s1);
    assert e1 != -1;
    int e2 = getRightEntity(s1);
    assert e2 > e1;
    int f1 = getLeftEntity(s2);
    assert f1 != -1;
    int f2 = getRightEntity(s2);
    assert f2 > f1;

    String[] fore1 = new String[e1];
    System.arraycopy(s1, 0, fore1, 0, e1);
    String[] fore2 = new String[f1];
    System.arraycopy(s2, 0, fore2, 0, f1);
    normalize(fore1, fore2);

    String[] intra1 = new String[e2 - e1 - 1];
    System.arraycopy(s1, e1 + 1, intra1, 0, e2 - e1 -1);
    String[] intra2 = new String[f2 - f1 - 1];
    System.arraycopy(s2, f1 + 1, intra2, 0, f2 - f1 -1);
    normalize(intra1, intra2);

    String[] after1 = new String[s1.length - e2 - 1];
    System.arraycopy(s1, e2 + 1, after1, 0, s1.length - e2 - 1);
    String[] after2 = new String[s2.length - f2 - 1];
    System.arraycopy(s2, f2 + 1, after2, 0, s2.length - f2 - 1);
    normalize(after1, after2);

    int nLenIntra = Math.min(Math.max(m_nIntra,
				      Math.max(m_nFore - 1, m_nAfter - 1)),
			     Math.min(intra1.length, intra2.length));
    double[] sk = stringKernel(intra1, intra2, nLenIntra, 1.0);
    double[] intraK = new double[nLenIntra];
    for (int i = 0; i < intraK.length; i++) {
      intraK[i] = sk[i] *
	Math.pow(m_lambda, intra1.length + 2 + intra2.length + 2);
    }
    
    double foreKernel = foreKernel(fore1, fore2, intraK);
    double intraKernel = intraKernel(intraK);
    double afterKernel = afterKernel(after1, after2, intraK);

    return foreKernel + intraKernel + afterKernel;
  }


  protected double foreKernel(String[] fore1, String[] fore2, double[] intraK)
  {
    double k = 0.0;
    double[] foreK = sKernel(fore1, fore2, m_nFore - 1, m_lambda);

    for (int i = 1; i < m_nFore; i++) {
      for (int j = 1; j <= m_nFore - i && j <= intraK.length; j++)
	k = k + foreK[i - 1] * intraK[j - 1];
    }

    return k;
  }


  protected double intraKernel(double[] intraK)
  {
    double k = 0.0;
    for (int i = 0; i < m_nIntra && i < intraK.length; i++)
      k = k + intraK[i];

    return k;
  }


  protected double afterKernel(String[] after1, String[] after2, double[] intraK)
  {
    String[] aft1 = mirror(after1);
    String[] aft2 = mirror(after2);
    
    double k = 0.0;
    double[] afterK = sKernel(aft1, aft2, m_nAfter - 1, m_lambda);
    
    for (int i = 1; i < m_nAfter; i++) {
      for (int j = 1; j <= m_nAfter - i && j <= intraK.length; j++)
	k = k + afterK[i - 1] * intraK[j - 1];
    }
    
    return k;
  }
  

  protected double[] stringKernel(String[] s, String[] t, int n, double lambda)
  {
    int slen = s.length;
    int tlen = t.length;
    
    double[][] K = new double[n + 1][slen * tlen];
    
    for (int j = 0; j < slen; j++)
      for (int k = 0; k < tlen; k++)
	K[0][k * slen + j] = 1;
    
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < slen - 1; j++) {
	double sum = 0.0;
	for (int k = 0; k < tlen - 1; k++) {
	  if (t[k] == s[j])
	    sum = lambda * (sum + lambda * K[i][k * slen + j]);
	  else
	    sum = lambda * sum;
	  K[i + 1][(k + 1) * slen + j + 1] = 
	    lambda * K[i + 1][(k + 1) * slen  + j] + sum;
	}
      }
    }

    double[] result = new double[n];
    for (int l = 0; l < result.length; l++) {
      result[l] = 0.0;
      for (int j = 0; j < slen; j++) {
	for (int k = 0; k < tlen; k++) {
	  if (t[k] == s[j])
	    result[l] = result[l] + K[l][k * slen + j] * lambda * lambda;
	}
      }
    }

    return result;
  }


  protected double[] sKernel(String[] s, String[] t, int n, double lambda)
  {
    int slen = s.length;
    int tlen = t.length;
    
    double[][] K = new double[n + 1][(slen + 1) * (tlen + 1)];
    
    for (int j = 0; j < slen + 1; j++)
      for (int k = 0; k < tlen + 1; k++)
	K[0][k * (slen + 1) + j] = 1;
    
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < slen; j++) {
	double sum = 0.0;
	for (int k = 0; k < tlen; k++) {
	  if (t[k] == s[j])
	    sum = lambda * (sum + lambda * K[i][k * (slen + 1) + j]);
	  else
	    sum = lambda * sum;
	  K[i + 1][(k + 1) * (slen + 1) + j + 1] = 
	    lambda * K[i + 1][(k + 1) * (slen + 1) + j] + sum;
	}
      }
    }

    double[] result = new double[n];
    for (int i = 0; i < result.length; i++)
      result[i] = K[i + 1][tlen * (slen + 1) + slen];
    return result;
  }


  protected int getLeftEntity(String[] s)
  {
    for (int i = 0; i < s.length; i++)
      if (s[i].equals("<p>"))
	return i;
    return -1;
  }


  protected int getRightEntity(String[] s)
  {
    for (int i = s.length - 1; i >= 0; i--)
      if (s[i].equals("<p>"))
	return i;
    return -1;
  }


  protected void normalize(String[] s1, String[] s2)
  {
    // normalize first string
    for (int i = 0; i < s1.length; i++) {
      for (int j = i + 1; j < s1.length; j++) {
	if (s1[j] != s1[i] && s1[j].equals(s1[i]))
	  s1[j] = s1[i];
      }
    }
    
    // normalize second string against first string
    for (int i = 0; i < s1.length; i++)
      for (int j = 0; j < s2.length; j++)
	if (s2[j] != s1[i] && s2[j].equals(s1[i]))
	  s2[j] = s1[i];
  }


  protected String[] mirror(String[] s)
  {
    String[] t = new String[s.length];
    for (int i = 0; i < s.length; i++)
      t[s.length - i - 1] = s[i];

    return t;
  }


  public static void main (String[] args)
  {
    //    String[] s1 = {"c", "a", "r", "<p1>", "c", "a", "r", "<p2>", "t", "r", "a"};
    //    String[] s2 = {"c", "a", "t", "<p1>", "c", "a", "t", "<p2>", "m", "r", "a"};
    String[] s1 = {"c", "c", "r", "<p>", "c", "d", "c", "<p>", "b", "c", "c"};
    String[] s2 = {"a", "a", "r", "<p>", "a", "d", "a", "<p>", "b", "a", "a"};
    RelationKernel rk = new RelationKernel();
    System.out.println(rk.kernel(s1, s2));
    rk.m_lambda = 1.0;
    System.out.println(rk.kernel(s1, s2));
  }

}

